The present invention relates to a first-in-first-out (FIFO) memory, and more particularly to an apparatus that maintains a count of the number of bytes in a FIFO memory that are filled with data.
FIFO memories, or simply FIFOs, are well know in the electronic data processing art. For example, FIFOs are commonly used to time-buffer data as it is transferred between systems or subsystems that have differing data and clock rates.
The first-in, first-out feature of all FIFOs allows data to be WRITTEN into the FIFO at will at a data input port, and READ from the FIFO at will at a data output port. Because of the freedom to WRITE and READ data at will, data overflow and underflow are major concerns. Data overflow occurs when more data is WRITTEN into a FIFO than it has capacity to store, and data underflow occurs when more data is READ from a FIFO than has been WRITTEN. To prevent data overflow and underflow problems, a FIFO usually is provided with some type of monitor which controls the data input gates and the data output gates to prevent any overflow or underflow.
Some FIFO monitors use WRITE counters to count the number of data words WRITTEN into the FIFO, and READ counters to count the number of data words READ from the FIFO. The WRITE and READ counters are regularly compared to see if their counts are the same, which is the underflow threshold condition, or if a difference between their counts is equal to the storage capacity of the FIFO, which is the overflow threshold condition. These comparisons between the counts of the two counters require large amounts of system time, especially the comparison that is made to the FIFO storage capacity after the READ count is subtracted from the WRITE count. With higher and higher speed peripherals and subsystems transferring larger and larger amounts of data, a FIFO monitor which is based on WRITE and READ counters will limit to the throughput of the FIFO.
Further, if the WRITE counters and READ counters counted data bytes instead of data words, then the dual counter type FIFO monitor becomes even slower because each counter must count or increment multiple times each time a data word is WRITTEN or READ. For example, if there are four data bytes to data word then four FIFO count cycles are required simply to update the counters. In addition to updating, subtraction and comparison must also be performed. Therefore, monitoring the byte capacity of a FIFO having multi-byte data words with a counter type monitor may take six or more FIFO clock cycles, which for large, high speed data throughputs is unacceptable.